//2807.在链表中插入最大公约数
//https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/?envType=daily-question&envId=2024-01-06
class Solution {
    //求最大公约数-辗转相除法
    // int getMax(int a,int b)
    // {
    //     if (b == 0) return a;
    //     return getMax(b, a % b);
    // }
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        if(!head->next) return head;
        ListNode* prev = head,*cur = head->next;
        while(cur)
        {
            int a = prev->val,b = cur->val,c = 0;
            while(b)
            {
                c = a%b;
                a=b;
                b=c;
            }
            ListNode* newNode = new ListNode(a);
            prev->next = newNode;
            newNode->next = cur;
            prev = cur;
            cur = cur->next;
        }
        return head;
    }
};
